package com.cqs.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.TimeUnit;

/**
 * Created by cqs on 2018/3/27.
 */
public class NetworkDelayTime {

    //Dijkstra算法
    private class Node {
        int point;
        int weight;

        public Node(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }
    }

    public int networkDelayTime(int[][] times, int N, int K) {
        K -= 1;
        //保存K到其他个点的距离
        int[] distances = new int[N];
        //构建邻接矩阵
        ArrayList<Node>[] adjacency = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adjacency[i] = new ArrayList<>();
            distances[i] = Integer.MAX_VALUE;
        }
        distances[K] = 0;
        for (int[] time : times) {
            int start = time[0] - 1;
            int end = time[1] - 1;
            int wight = time[2];
            adjacency[start].add(new Node(end, wight));
            if (start == K) {
                distances[end] = wight;
            }
        }
        Set<Integer> used = new HashSet<>();
        Set<Integer> unused = new HashSet<>();
        //点归入结合
        for (int i = 0; i < N; i++) {
            unused.add(i);
        }
        int minPoint = K;//unused集合中离节点K最近的点

        while (unused.size() > 0) {
            //寻找下一个点
            int min = Integer.MAX_VALUE;
            for (Integer i : unused) {
                if (distances[i] < min) {
                    min = distances[i];
                    minPoint = i;
                }
            }
            if (min == Integer.MAX_VALUE) return -1;
//            println(distances);
            unused.remove(minPoint);
            used.add(minPoint);
            ArrayList<Node> list = adjacency[minPoint];
            for (Node node : list) {
                //更新距离
                if (distances[node.point] > (node.weight + distances[minPoint])) {
                    distances[node.point] = node.weight + distances[minPoint];
                }
            }

        }
        int max = distances[0];
        for (int i = 1; i < used.size(); i++) {
            if (distances[i] == Integer.MAX_VALUE) {
                return -1;
            }
            if (distances[i] > max) {
                max = distances[i];
            }
        }
        return max;
    }

//    static void println(int[] list) {
//        for (int i : list) {
//            System.out.print(i + "\t");
//        }
//        System.out.println();
//
//    }

    public static void main(String[] args) {
        int[][] times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        int[][] times1 = {{1,2,1}};
        int N = 4;
        int K = 2;
        NetworkDelayTime time = new NetworkDelayTime();

        int result = time.networkDelayTime(times, N, K);
        System.out.println(result);
    }
}
